package core;

import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Solves the Flow Graph Max flow problem using the Ford Folkerson algorithm.
 * @author Michael Pitts
 */
public class FFAlt {
	
	/** Gets a MaxFlowSolver which can be used to call this classes solve method.*/
	public static MaxFlowSolver getSolver() {
		return new MaxFlowSolver() {
			public double solve(final SimpleGraph the_graph) {
				return FFAlt.solve(the_graph, false);
			}
			public String getName() {
				return "Ford Fulkerson Alternate";
			}};
	}
	
	/** Gets a MaxFlowSolver which can be used to call this classes solve method.
	 * Gets the scaling version of Ford Fulkerson.*/
	public static MaxFlowSolver getSolverScale() {
		return new MaxFlowSolver() {
			public double solve(final SimpleGraph the_graph) {
				return FFAlt.solve(the_graph, true);
			}
			public String getName() {
				return "Scaling Ford Fulkerson Alternate";
			}};
	}
	
	/** Only needed to instance inner classes.*/
	private FFAlt() {/*do nothing*/}
	
	/**
	 * Finds the maximum flow from source to sink on the given graph.
	 * @param the_graph is the SimpleGraph on which to solve.
	 * @param scale if true, uses scaling Ford Fulkerson, otherwise normal.
	 * @return is the maximum flow over the graph.
	 */
	public static double solve(final SimpleGraph the_graph, final boolean scale) {
		final FFData data = new FFAlt().new FFData(the_graph, scale);
		FlowPath path = getPath(the_graph, data);
		while(data.getDelta() > 0) {
			if (path != null) data.augument(path);
			else data.reduceDelta();
			path = getPath(the_graph, data);
		}
		return data.getMaxFlow();
	}
	
	/**
	 * Gets a path along the residual graph from the source to the sink.
	 * @param the_graph is the graph the residuals are based on.
	 * @param data is the object storing the flow, and other relevant data.
	 * @return a new FlowPath object if a path was found, null otherwise.
	 */
	private static FlowPath getPath(final SimpleGraph the_graph, final FFData data) {
		return search(the_graph, data, data.getSource(), data.getSink(), new HashSet<Vertex>());
	}

	/**
	 * Searches for one edge in a potential path from start to end.  Effectively is
	 * a depth first search.
	 * @param the_graph is the underlying graph the search is performed on.
	 * @param data is the data relevant to the search, such as flow.
	 * @param start is where the search is to begin from.
	 * @param end is where the search is trying to go.
	 * @param visited stores the Vertex objects that have been visited.
	 * @return a new FlowPath object if a recursive path to end was found, otherwise
	 * returns null.
	 */
	@SuppressWarnings("unchecked")
	private static FlowPath search(final SimpleGraph the_graph, final FFData data,
			final Vertex start, final Vertex end, final Set<Vertex> visited) {
		visited.add(start);
		boolean back_edge; //if true, the edge e is a back edge
		double residual; // the residual capacity of edge e
		FlowPath path; // stores the path from the sink to other, if null no path
		Vertex other; // the node on the other side of e from start
		for (Edge e : ((List<Edge>)start.incidentEdgeList)) {
			back_edge = e.getSecondEndpoint().equals(start);
			other = the_graph.opposite(start, e);
			if (!visited.contains(other)) { // don't go back on path
				residual = isAcceptibleEdge(start, e, back_edge, data);
				if (residual > 0) { // potentially viable to travel down edge
					if (end.equals(other)) { // found the sink
						return new FFAlt().new FlowPath(e, residual);
					} else { // internal node, depth first search more
						 path = search(the_graph, data, other, end, visited);
						 if (path != null) { // found a path, add this edge
							 path.addEdge(e, residual);
							 return path;
						 } // else could not find a path down the edge
					}
				}
			}
		}
		return null; // found no path
	}

	/**
	 * Determines if a given edge is acceptable to add in a path by finding the 
	 * residual flow along the given edge.  Returns zero if a path can not be made 
	 * in the given direction along the_edge, otherwise returns a positive value of
	 * the residual along the_edge.
	 * @param start is the current Vertex of interest.
	 * @param the_edge is the Edge under consideration.
	 * @param back_edge is true if the edge points away from start, false otherwise.
	 * @param data stores relevant data to the graph, such as flow.
	 * @return a positive number which represents the available capacity, or zero 
	 * if there is no capacity left in the desired direction.
	 */
	private static double isAcceptibleEdge(final Vertex start, final Edge the_edge,
			final boolean back_edge, final FFData data) {
		final double residual;
		if (back_edge)residual = data.getFlow(the_edge); // reverse edge residual
		else residual = ((Double)the_edge.getData()) - data.getFlow(the_edge); // forward residual
		if (residual >= data.getDelta()) return residual;
		return 0.0;
	}

	/**
	 * Stores the flow along all edges, as well as the maximum flow for a graph.
	 * @author Michael Pitts
	 */
	private class FFData {
		/** Store the flow along each edge.*/
		private final Map<Edge, Double> my_map;
		
		/** Stores the total maximum flow to the sink.*/
		private double my_max_flow;
		
		/** The minimum capacity a residual must have to be added to a path.*/
		private int my_delta;
		
		/** The source Vertex.*/
		private Vertex my_source;
		
		/** The sink Vertex.*/
		private Vertex my_sink;
		
		/**
		 * Creates a new FlowMap based on the given SimpleGraph.
		 * @param the_graph is the graph to base the map on.
		 * @param scale if true, will initialize delta to the capacity of all edges 
		 * adjacent to the source, otherwise delta will be one.
		 */
		@SuppressWarnings("unchecked")
		public FFData(final SimpleGraph the_graph, final boolean scale) {
			my_map = new HashMap<Edge, Double>();
			my_max_flow = 0.0;
			for (Edge e : ((List<Edge>)the_graph.edgeList)) my_map.put(e, 0.0);
			for (Vertex v : ((List<Vertex>)the_graph.vertexList)) {
				if ("s".equalsIgnoreCase((String)v.getName())) my_source = v;
				else if ("t".equalsIgnoreCase((String)v.getName())) my_sink = v;
			}
			if (scale) {
				for (Edge e : ((List<Edge>)my_source.incidentEdgeList))
					my_delta += ((Double)e.getData());
			} else
				my_delta = 1;
		}
		
		/** Gets the source node of the graph.*/
		public Vertex getSource() {return my_source;}
		
		/** Gets the sink node of the graph.*/
		public Vertex getSink() {return my_sink;}
		
		/** Gets the maximum flow to the sink.*/
		public double getMaxFlow() {return my_max_flow;}
		
		/**
		 * Augments the flow on the graph over the given FlowPath.
		 * @param the_path is the particular path to augment.
		 */
		public void augument(final FlowPath the_path) {
			boolean back_edge = false; // true if old_edge was a back edge
			final double bottle_neck = the_path.getBottleNeck();
			final Iterator<Edge> itr = the_path.iterator();
			Edge old_edge, edge = itr.next(); // first edge is always from source
			my_map.put(edge, my_map.get(edge)+ bottle_neck);
			// adds flow from source to first edge, always forward
			while (itr.hasNext()) {
				old_edge = edge;
				edge = itr.next();
				back_edge = isBack(old_edge, edge, back_edge);
				if (back_edge) my_map.put(edge, my_map.get(edge) - bottle_neck);
				else my_map.put(edge, my_map.get(edge) + bottle_neck);
			}
			my_max_flow += bottle_neck;
		}
		
		/** Gets the flow along the given edge.*/
		public double getFlow(final Edge the_edge) {
			return my_map.get(the_edge);
		}

		/**
		 * Gets if edge is a back edge or not.
		 * @param old_edge is the previous edge.
		 * @param edge is the current Edge.
		 * @param back_edge is true if old_edge was a back edge.
		 * @return true if edge is a back edge, false otherwise.
		 */
		private boolean isBack(final Edge old_edge, final Edge edge,
				final boolean back_edge) {
			if (back_edge)
				return old_edge.getFirstEndpoint().equals(edge.getSecondEndpoint());	
			return old_edge.getSecondEndpoint().equals(edge.getSecondEndpoint());
		}
		
		/** Gets the current delta value, which represents the minimum residual 
		 * capacity for an edge to to be added to a path. */
		public int getDelta() {return my_delta;}
		
		/**
		 * Divides the current delta value by two, and returns the new value.
		 * @return the new value of delta.
		 * @see FFData#getDelta()
		 */
		public int reduceDelta() {
			my_delta /= 2; 
			return getDelta();
		}
	}
	
	/**
	 * Stores Edges for a given flow, and the bottleneck of that flow.  Edges are 
	 * added in reverse order, from sink to source, but iterate in normal order, 
	 * from source to sink.
	 * @author Michael Pitts
	 * @see util#Stack
	 */
	private class FlowPath implements Iterable<Edge> {
		/** The list of edges.*/
		private final Deque<Edge> my_flow;
		
		/** The minimum residual from all the edges.*/
		private double my_bottle_neck;
		
		/**
		 * Creates a new FlowPath, with the final Edge of the path used during 
		 * construction.
		 * @param the_final_edge is the final edge in the path, the path to t.
		 * @param residual is the residual along the edge.
		 */
		public FlowPath(final Edge the_final_edge, final double residual) {
			my_flow = new LinkedList<Edge>();
			my_flow.add(the_final_edge);
			my_bottle_neck = residual;
		}
		
		/**
		 * Gets the bottleneck of the flow.
		 * @return the smallest residual from the whole flow.
		 */
		public double getBottleNeck() { return my_bottle_neck;}
		
		/**
		 * Adds an Edge to the front of the flow.
		 * @param the_edge is the Edge to add.
		 * @param residual is the residual of the Edge.
		 */
		public void addEdge(final Edge the_edge, final double residual) {
			if (residual < my_bottle_neck) my_bottle_neck = residual;
			my_flow.addFirst(the_edge);
		}

		@Override public Iterator<Edge> iterator() {return my_flow.iterator();}
	}
}
